package Tree;

/**
 * 114.二叉树展开为链表
 * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
 * ● 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
 * ● 展开后的单链表应该与二叉树 先序遍历 顺序相同。
 */
public class flatten {
    /**
     * hot100一刷
     */
    static class Solution {
        TreeNode prev = null;

        public void flatten(TreeNode root) {
            if (root == null)
                return;
            // 先处理右子树，再处理左子树（后序遍历的思路）
            flatten(root.right);
            flatten(root.left);
            // 调整指针：将当前节点的right指针指向prev；left置空
            root.right = prev;
            root.left = null;
            // 更新prev
            prev = root;
        }
    }


    /**
     * hot100二刷
     */
    public void flatten(TreeNode root) {
        dfs(root);
    }

    public TreeNode dfs(TreeNode root) {
        if (root == null)
            return root;
        TreeNode l = dfs(root.left);
        TreeNode r = dfs(root.right);
        if (l != null) {
            l.right = root.right;
            root.right = root.left;
            root.left = null;
        }
        return r != null ? r : l != null ? l : root;

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        solution.flatten(root);

    }

}
